package org.flint.summary.algs;

/**
 * @author flint92
 */
public class NQueen {

    // 棋盘格子的范围以及皇后的数量
    private final int num;

    // 用一个二维数组来表示棋盘
    // 0表示没有落子 1表示放置了皇后
    private int[][] chessBoard;

    public NQueen(int num) {
        if (num <= 0) {
            throw new IllegalArgumentException("num must greater than zero");
        }
        this.num = num;
        chessBoard = new int[num][num];
    }

    /**
     * 检查落点是否符合规则
     *
     * @param x x
     * @param y y
     * @return bool
     */
    private boolean check(int x, int y) {
        for (int i = 0; i < y; i++) {
            // 检查纵向
            if (chessBoard[x][i] == 1) {
                return false;
            }
            // 检查左侧斜向
            if (x - 1 - i >= 0 && chessBoard[x - 1 - i][y - 1 - i] == 1) {
                return false;
            }
            // 检查右侧斜向
            if (x + 1 + i < num && chessBoard[x + 1 + i][y - 1 - i] == 1) {
                return false;
            }
        }
        return true;
    }

    public boolean settleQueen() {
        return settleQueen(0);
    }

    private boolean settleQueen(int y) {
        // 行数到达最后一行 说明已经找出答案
        if (y == num) {
            return true;
        }
        // 深度遍历
        for (int i = 0; i < num; i++) {
            // 检查是否符合规则， 如果符合 更改元素值并进一步递归
            if (check(i, y)) {
                chessBoard[i][y] = 1;
                // 递归如果返回true 说明下层已经找到解决方法，无需继续循环
                if (settleQueen(y + 1)) {
                    return true;
                }
            }
            // 为当前行清零 以免在回溯的时候出现脏数据
            for (int j = 0; j < num; j++) {
                chessBoard[j][y] = 0;
            }
        }
        return false;
    }

    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder();
        for (int i = 0; i < num; i++) {
            for (int j = 0; j < num; j++) {
                sb.append(chessBoard[i][j]).append(" ");
            }
            sb.append("\n");
        }
        return sb.toString();
    }

    public static void main(String[] args) {

        NQueen queen = new NQueen(4);
        if (queen.settleQueen()) {
            System.out.println(queen.toString());
        } else {
            System.out.println("has no solution to settle queen.");
        }
    }
}
